//
//  main.c
//  Chapter_1
//
//  Created by hao on 18/3/15.
//  Copyright © 2018年 hao. All rights reserved.
//

#include <stdio.h>
#include "maxSubSum.h"
#include "twoPointLookup.h"
#include "singlyLinkedList.h"
#include "stackImp.h"
#include "queueImp.h"
#include "treeImp.h"

// 当递归次数达到一定数量级就会崩溃(栈溢出),因为每一次递归调用都会保存上一次的函数状态
void test_digui(int num)
{
    if (num) {
        test_digui(num-1);
        printf("num = %d \n", num);
    }
}

void test_max_sub_sum()
{
//    int s[] = {1, 4, -2, -3, 6, 1, 0, -7, 3};
    int s[] = {4, -3, 5, -2, -1, 2, 6, -2};
    int max = maximumSubsequenceSum1(s, 8);
//    int max = maximumSubsequenceSum2(s, 9);
    printf("max = %d \n", max);
}

void test_erfen()
{
    // 不是结构体指针直接赋值
//    struct test_struct *s1 = (struct test_struct *)malloc(sizeof(struct test_struct));
    int size = 8;
    ElementType data_arr[] = {5, 6, 11, 16, 29, 45, 60, 81};
    // 结构体指针需要初始化
    List list = (List)malloc(sizeof(struct LNode));
    // 因为List是指针类型的结构体，赋值成员数组data[]时，必须使用memcpy()复制, 直接赋值报错 Array type 'ElementType [10]' is not assignable
    // 参数三是内存占用空间, 如int占4个字节，数组有八个数，就要传4*8
    memcpy(list->data, data_arr, sizeof(ElementType)*size);
    list->last = size-1;
    int postion = twoPointLookup(list, 81);
    printf("postion = %d \n", postion);
    
    printf("delete before %d, %d \n", list->data[2], list->data[3]);
    deleteElemInList(3, list);
    printf("delete after %d, %d \n", list->data[2], list->data[3]);
    
    insertElement(10, 4, list);
    printf("insert after %d, %d \n", list->data[2], list->data[3]);
    
    int index = findElement(29, list);
    printf("find index = %d \n", index);
}

void test_singly_linked_list()
{
    SinglyList list2 = makeSinglyList();
    list2->data = 30;
    // 没有next一定要指向NULL，不然判断 list2->next == NULL 判断不了, 不指向NULL的话会产生野指针
    list2->next = NULL;
    printf("list2 = %p \n", list2);
    
    SinglyList list1 = makeSinglyList();
    list1->data = 20;
    list1->next = list2;
    
    SinglyList list0 = makeSinglyList();
    list0->data = 10;
    list0->next = list1;
    
//    printf("find postion = %d \n", find(0, list0));
    
    int len = singlyListLength(list0);
    printf("length = %d \n", len);
    printfSinglyList(list0);
    
    SinglyList findList = findKthInSinglyList(3, list0);
    printfSinglyList(findList);
    
    SinglyList findElem = findElemInSinglyList(0, list0);
    printfSinglyList(findElem);
    
    SinglyList insertList = insertInSinglyList(24, 3, list0);
    printfSinglyList(insertList);
//    printf("insertInSinglyList: data = %d \n", findKthInSinglyList(3, insertList)->data);
    
    printfSinglyList(deleteElemInSinglyList(4, insertList));
    
//    printf("list2 = %d \n", list2->data);
    
//    free(list0);
//    free(list1);
//    free(list2);
}

void test_stack_imp()
{
    StackList s1 = createStack();
    pushStackList(10, s1);
    pushStackList(11, s1);
    pushStackList(12, s1);
    printfSinglyList(s1);
//    printf("s1 = %p \n", s1);
//    printf("s1->next = %p \n", s1->next);
//    printf("s2 = %p \n", s1);
//    printf("s3 = %p, s2 = %p, s3 = %p \n", s1, s1->next, s1->next->next);
    
//    ElementType value = popStackList(s1);
//    printf("value = %d \n", value);
//    printfSinglyList(s1);
//    printf("s1 = %p \n", s1);
//    printf("s1->next = %p \n", s1->next);
//    ElementType value2 = popStackList(s1);
//    printf("value2 = %d \n", value2);
//    printfSinglyList(s1);
    
    ElementType value = TestPopStackList(&s1);
    TestPopStackList(&s1);
    TestPopStackList(&s1);
    TestPopStackList(&s1);
    TestPopStackList(&s1);
    printf("value = %d \n", value);
    printfSinglyList(s1);
    printf("s1 = %p \n", s1);
}

void test_queue_imp()
{
    QueueList queueList = createQueueList();
    addValueInQueue(10, queueList);
    addValueInQueue(20, queueList);
    addValueInQueue(30, queueList);
    printfSinglyList(queueList->fornt);
    
    ElementType elem = deleteInQueue(queueList);
    ElementType elem2 = deleteInQueue(queueList);
    printf("elem = %d, elem2 = %d \n", elem, elem2);
    printfSinglyList(queueList->fornt);
    
    addValueInQueue(40, queueList);
    addValueInQueue(50, queueList);
    printfSinglyList(queueList->fornt);
}

void test_polynomial()
{
    int p1Coeffs[] = {3, 4, -1, 2, -1};
    int p1Exps[] = {5, 4, 3, 1, 0};
    
    int p2Coeffs[] = {2, 1, -7, 1};
    int p2Exps[] = {4, 3, 2, 1};
    
    PolynomialNode p1 = createPolynomialList(p1Coeffs, p1Exps, 5);
    PolynomialNode p2 = createPolynomialList(p2Coeffs, p2Exps, 4);
    
    prinftPolynomial(p1);
    prinftPolynomial(p2);
    
    prinftPolynomial(polyAdd(p1, p2));
}

void test_tree_imp()
{
//    Tree tree = createTreeOnPreMidOrder("ABDFECGHI", "DBEFAGHCI");
//    Tree tree = createTreeOnPreMidOrder("abcdefghij", "cbedahgijf");
//    printf("data = %c \n", tree->left->right->left->charData);
//    Tree midSufTree = createTreeOnMidAndSuffixOrder("DBEFAGHCI", "DEFBHGICA");
    Tree midSufTree = createTreeOnMidAndSuffixOrder("cbedahgijf", "cedbhjigfa");
    printf("\n");
}

int main(int argc, const char * argv[]) {
    // insert code here...
//    test_digui(1000000);
//    test_max_sub_sum();
//    test_erfen();
//    test_singly_linked_list();
//    test_stack_imp();
//    test_queue_imp();
//    test_polynomial();
    test_tree_imp();
    return 0;
}
